package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.List;

/**
 * leetcode 530. 二叉搜索树的最小绝对差
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/4 9:03
 */
public class E530 {
    /*
                    236
                   /   \
                 104   701
                /  \   /  \
                  227    911
    */

    /**
     * <h3>方法一，遍历统计每个路径，上述情况处理不了</h3>
     * @param root 树根节点
     * @return 最小绝对差
     */
    public int getMinimumDifference1(TreeNode root) {
        // 递归结束条件：当前树为空，返回Integer的最大值
        if (root == null){
            return Integer.MAX_VALUE;
        }
        // 递的时候找左子树的最小绝对差
        int leftTree = getMinimumDifference1(root.left);
        // 递的时候找右子树的最小绝对差
        int rightTree = getMinimumDifference1(root.right);
        // 归的时候比较左子树和右子树的最小绝对差，取最小值
        int minTree = Math.min(leftTree, rightTree);
        // 归的时候再让上述最小值与左子节点右子节点的路径作比较取最小值返回
        int left = root.left == null ? Integer.MAX_VALUE : Math.abs(root.val - root.left.val);
        int right = root.right == null ? Integer.MAX_VALUE : Math.abs(root.val - root.right.val);
        return Math.min(minTree, Math.min(left, right));
    }

    /**
     * <h3>方法二，中序遍历，因为中序遍历结果就是升序排序，只需要统计相邻节点之差</h3>
     * @param root 树根节点
     * @return 最小绝对差
     */
    public int getMinimumDifference2(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inOrder(root, list);
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < list.size() - 1; i++) {
            int sub = Math.abs(list.get(i + 1) - list.get(i));
            if (sub < min){
                min = sub;
            }
        }
        return min;
    }

    /**
     * 中序遍历
     * @param root 根节点
     * @param list 存储升序结果的集合
     */
    private void inOrder(TreeNode root, List<Integer> list) {
        if (root == null){
            return;
        }
        inOrder(root.left, list);
        list.add(root.val);
        inOrder(root.right, list);
    }

    /**
     * <h3>方法三，优化中序遍历</h3>
     * @param root 树根节点
     * @return 最小绝对差
     */
    public int getMinimumDifference3(TreeNode root) {
        inOrder(root);
        return minDiff;
    }

    private int prev = -1; // 记录排序结果中当前节点前一个节点的值
    private int minDiff = Integer.MAX_VALUE; // 记录最小差值

    /**
     * 优化后的中序遍历
     * @param root 当前树根节点
     */
    private void inOrder(TreeNode root){
        if (root == null){
            return;
        }
        inOrder(root.left);
        if (prev != -1){
            minDiff = Math.min(minDiff, Math.abs(root.val - prev));
        }
        prev = root.val;
        inOrder(root.right);
    }
}
